package h0830;

public class QuickSortHoareLeftPivot {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi-1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 最左边的元素作为枢纽元
        int i = low;
        int j = high;
        while (i<=j) {
            while (i<=high&&arr[i]<=pivot){
                i++;
            }
            while (j>=low&&arr[j]>pivot){
                j--;
            }
            if (i>=j) break;
            swap(arr, i, j);
            i++;
            j--;
        }
        //如果选取右边元素为基准
//        swap(arr, high, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
